// Created by WXX on 2021/11/30 15:09
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：24 ms, 在所有 C++ 提交中击败了95.53%的用户
 * 内存消耗：16.1 MB, 在所有 C++ 提交中击败了79.68%的用户
 */
class Solution {
public:
    vector<vector<int>> allCellsDistOrder(int n, int m, int r, int c) {
        vector<vector<int>> res(1, {r, c});

        int dx[4] = {1, 1, -1, -1}, dy[4] = {1, -1, -1, 1};

        for (int d = 1; ; d++) {  // 枚举x距离中心点的距离d
            int x = r - d, y = c, cnt = 0;  // 从(x, y)顺时针枚举菱形
            for (int i = 0; i < 4; i++) {  // 枚举四个方向
                for (int j = 0; j < d; j++) {  // 每个方向有d个数据
                    if (x >= 0 && x < n && y >= 0 && y < m) {
                        res.push_back({x, y});
                        cnt++;
                    }
                    x += dx[i], y += dy[i];
                }
            }
            if (!cnt) break;
        }

        return res;
    }
};

void OutputBasicArray2D1(vector<vector<int>> nums) {

    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << "[";
        for (int j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ", ";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    OutputBasicArray2D1(Solution().allCellsDistOrder(2, 3, 1, 2));

    return 0;
}
